Floyd Warshall Algorithm

contents

플로이드-워셜 알고리즘은 컴퓨터 과학에서 모든 쌍 최단 경로(All-Pairs Shortest Path, APSP) 문제를 해결하는 데 사용되는 핵심 알고리즘입니다. 다익스트라(Dijkstra)가 하나의 정점에서 다른 모든 정점까지의 경로를 구하는 반면, 플로이드-워셜은 그래프 내의 모든 정점 쌍 사이의 최단 경로를 한 번에 구합니다.

1. 핵심 개념: 동적 계획법 (Dynamic Programming)

이 알고리즘은 동적 계획법(DP) 에 기반을 둡니다. "거쳐가는 중간 정점(Intermediate vertex)"의 허용 범위를 점차 늘려가며 해답을 바텀업(Bottom-up) 방식으로 구축합니다.

핵심 질문:

"정점 $1$부터 $k$까지만 중간 경유지로 사용할 수 있을 때, 정점 $i$에서 정점 $j$로 가는 최단 거리는 얼마인가?"

각 단계 $k$에서 알고리즘은 다음 두 가지 경우 중 더 적은 비용이 드는 것을 선택합니다.

1. 이전 단계($1...k-1$)의 경유지들만 사용하여 $i$에서 $j$로 가는 경우.
2. $i$에서 $k$를 거쳐서, $k$에서 $j$로 가는 경우.

2. 수학적 원리 (점화식)

정점의 개수를 $V$라고 합시다. 우리는 거리를 저장할 2차원 배열(행렬)을 유지합니다.

$dist[i][j]$를 정점 $i$에서 정점 $j$까지의 최단 거리라고 정의합니다.

초기화:

• $dist[i][j] = w(i, j)$ (간선이 존재할 경우 가중치)
• $dist[i][j] = \infty$ (간선이 없을 경우 무한대)
• $dist[i][i] = 0$ (자기 자신으로의 거리는 0)

점화식 (Recurrence Relation):

모든 쌍 $(i, j)$와 모든 중간 정점 $k$에 대하여:

$$dist[i][j] = \min(dist[i][j], \quad dist[i][k] + dist[k][j])$$

이 식의 의미는 다음과 같습니다: "현재 알고 있는 직행 경로(좌변)가 정점 $k$를 거쳐서 가는 우회 경로(우변)보다 더 긴가?" 만약 우회 경로가 더 짧다면 거리를 갱신합니다.

3. 알고리즘 (단계별 설명)

플로이드-워셜의 가장 큰 장점은 구현이 매우 간단하다는 점입니다. 3중 반복문(Loop)으로 구성됩니다.

반복문 순서의 중요성: $k$ (중간 정점)를 다루는 반복문은 반드시 가장 바깥쪽에 위치해야 합니다. 이는 $k$번째 정점을 고려할 때, 이미 $1$부터 $k-1$까지의 정점을 거치는 최단 경로들이 모두 계산되어 있음을 보장하기 위함입니다.

의사코드 (Pseudocode)

dist 배열을 |V| x |V| 크기로 만들고 무한대(또는 간선 가중치)로 초기화

for k from 1 to |V|:          // 거쳐가는 중간 정점
    for i from 1 to |V|:      // 출발 정점
        for j from 1 to |V|:  // 도착 정점
            
            // 만약 정점 k를 거쳐가는 것이 i에서 j로 가는 기존 경로보다 빠르다면,
            // dist[i][j] 값을 갱신한다.
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

4. 경로 재구성 (Path Reconstruction)

단순히 비용(거리)만 구하는 것이 아니라 실제 경로를 알고 싶을 때가 많습니다. 이를 위해 직전 정점 행렬(Predecessor Matrix)(보통 next 또는 parent라고 함)을 유지합니다.

1. 초기화: 간선이 있다면 next[i][j] = j, 없다면 null.
2. 반복문 내부에서 거리가 갱신될 때, 경로 정보도 함께 갱신합니다:

if dist[i][j] > dist[i][k] + dist[k][j]:
    dist[i][j] = dist[i][k] + dist[k][j]
    next[i][j] = next[i][k]  // i에서 j로 가려면, 우선 i에서 k로 가는 첫 정점으로 이동해야 함

$u$에서 $v$까지의 경로 복원:

1. $u$에서 시작합니다.
2. next[u][v]를 봅니다. 이 값을 $x$라고 합시다.
3. $x$를 출력합니다.
4. 이제 next[x][v]를 봅니다.
5. $v$에 도달할 때까지 반복합니다.

5. 구현 예제 (Python)

음수 사이클 감지 기능을 포함한 깔끔한 구현 예제입니다.

INF = float('inf')

def floyd_warshall(graph, V):
    # 거리 배열 초기화
    dist = [[INF] * V for _ in range(V)]
    
    # 그래프 간선 정보를 기반으로 거리 초기화
    # graph가 인접 행렬이나 유사한 구조라고 가정
    for i in range(V):
        dist[i][i] = 0
        for j, weight in graph[i]:
            dist[i][j] = weight
            
    # 핵심 알고리즘 (3중 반복문)
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # 최적화: k를 거쳐가는 경로가 불가능하면 스킵
                if dist[i][k] == INF or dist[k][j] == INF:
                    continue
                    
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    # 음수 사이클(Negative Cycle) 감지
    for i in range(V):
        if dist[i][i] < 0:
            print("음수 사이클이 감지되었습니다!")
            return None
            
    return dist

6. 복잡도 분석

시사점:

• 간선이 매우 많은 밀집 그래프(Dense Graph, $E \approx V^2$) 에 적합합니다.
• 정점의 개수가 매우 많은 경우(예: $V > 500$ 또는 $1000$)에는 $O(V^3)$ 때문에 너무 느려서 사용하기 어렵습니다.

7. 음수 사이클 (Negative Cycles)

음수 사이클이란 사이클 내의 간선 가중치 합이 음수가 되는 루프를 말합니다. 이 구간을 계속 돌면 "최단 경로" 비용이 $-\infty$가 되어버립니다.

플로이드-워셜은 (다익스트라와 달리) 음수 가중치 간선을 처리할 수 있지만, 음수 사이클이 존재하면 정상적인 경로를 구할 수 없습니다.

감지 방법:

알고리즘 수행 후, 대각선 요소인 $dist[i][i]$를 확인합니다.

• 정상적인 경우, 자기 자신으로의 거리는 $0$이어야 합니다.
• 만약 $dist[i][i] < 0$이라면, 이는 $i$에서 출발해 다시 $i$로 돌아오는 경로의 비용이 음수라는 뜻이므로, 음수 사이클이 존재함을 의미합니다.

요약 비교

references